package Array;

import java.util.*;

/**
 * 1. Two Sum
 * https://leetcode.com/problems/two-sum/
 *
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 *
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 *
 * Example:
 *
 * Given nums = [2, 7, 11, 15], target = 9,
 *
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 *
 * # 题目大意
 * 在数组中找到 2 个数之和等于给定值的数字，结果返回 2 个数字在数组中的下标。
 *
 * # 解题思路
 * 这道题最优的做法时间复杂度是 O(n)。
 *
 * 顺序扫描数组，对每一个元素，在 map 中找能组合给定值的另一半数字，如果找到了，直接返回 2 个数字的下标即可。
 * 如果找不到，就把这个数字存入 map 中，等待扫到“另一半”数字的时候，再取出来返回结果。
 *
 */
public class E_1_两数之和 {
    public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map temp = new HashMap<Integer, Integer>();
        temp.put(nums[0], 0);
        for (int i = 1; i < nums.length; i++) {
            if (temp.get(target-nums[i]) != null) {
                result[0] = (int) temp.get(target-nums[i]);
                result[1] = i;
                break;
            } else {
                temp.put(nums[i], i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[]{1, 2, 3, 4, 5}, 9)));
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
    }
}
